package Q868;

import java.util.Random;

public class Test {
    public static void main(String[] args) {
        int i = new Solution1().binaryGap(22);
        System.out.println(i);
    }
}

class Solution1 {
    public int binaryGap(int n) {
        String s = Integer.toBinaryString(n);
        System.out.println(s);
        char[] chars = s.toCharArray();
        int max = 0;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == '1') {
                max = i;
                break;
            }
        }
        if(max == 0){
            return max;
        }
        return max;
    }

    public int binaryGap2(int n) {
        String binStr = Integer.toBinaryString(n);
        int lastOneIdx = n, max = 0;
        for (int i = 0; i < binStr.length(); i++) {
            if (binStr.charAt(i) == '1') {
                max = Math.max(max, i - lastOneIdx);
                lastOneIdx = i;
            }
        }
        return max;
    }

}

class Solution2 {
    int[]arr;
    public Solution2(int[] nums) {
        arr=nums.clone();
    }
    public int pick(int target) {
        int count=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]==target) count++;
        }
        int choose=new Random().nextInt(count)+1;
        count=0;
        for(int i=0;i<arr.length;i++){
            if(arr[i]==target){
                count++;
                if(count==choose) return  i;
            }
        }
        return  -1;
    }
}
